package ljl.alg.jianzhioffer.round3.medium;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class _7_buildTree {


    class v1 {

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return doBuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        TreeNode doBuild(int[] pre, int pl, int pr, int[] in, int inl, int inr) {
            if (pl > pr)
                return null;
            TreeNode root = new TreeNode(pre[pl]);
            int llen = 0;
            while (in[inl + llen] != pre[pl])
                llen++;
            root.left = doBuild(pre, pl + 1, pl + llen, in, inl, inl + llen - 1);
            root.right = doBuild(pre, pl + llen + 1, pr, in, inl + llen + 1, inr);
            return root;
        }
    }

    class lufei {
        int[] preorder;
        Map<Integer, Integer> inorderIndexes = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for (int i = 0; i < inorder.length; i++) {
                inorderIndexes.put(inorder[i], i);
            }
            return build(0, 0, preorder.length - 1);
        }
        private TreeNode build(int preorderRootPos, int left, int right) {
            if (left > right)
                return null;
            TreeNode res = new TreeNode(preorder[preorderRootPos]);
            int inorderPos = inorderIndexes.get(preorder[preorderRootPos]);
            res.left = build(preorderRootPos + 1, left, inorderPos - 1);
            res.right = build(preorderRootPos + inorderPos - left + 1, inorderPos + 1, right);
            return res;
        }
    }
}
